////////////////////////////////////////////////////////////////////
//	
//	File: c4convert.chpl 
//	Team: Patrick Copeland, Deanna Fink, Jordan Hildebrandt
//	Date: 25 January 2012
//	Time: 21:50
//	Desc: An implementation of Connect4 in Chapel
////////////////////////////////////////////////////////////////////


use Random, Time;

const NUM_COLS : int = 7;   
const NUM_ROWS : int = 6;


proc playGame(state, initialCurrPlayerSymbol, playerXDef, playerODef){
	var gameOver : bool = false;
	var currPlayerSymbol = initialCurrPlayerSymbol;
	
	var terminalResults : string;		//variable pre-definition
	var copiedState : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
	var playerMove : int;	
	
	while(!gameOver){
		printState(state);
		
		// Copy the state, so the playerDef getMove function can change it if it wants
		//copiedState[0..NUM_COLS][0..NUM_ROWS] = state[0..NUM_COLS][0..NUM_ROWS];
		copiedState = stateCopy(state);
		if(currPlayerSymbol == 'x'){
			playerMove = playerXDef.getMove(copiedState);
		} else {
			playerMove = playerODef.getMove(copiedState);
		}
      
		writeln("=========================================");
	
		//Check if game is over...
		if (!isValidMove(state, playerMove)){
			writeln("**************\nInvalid move\n**************\n");
			terminalResults = otherPlayer(currPlayerSymbol);
			gameOver = true;
		} else {
			// Make the move actually occur
 			move(state, playerMove, currPlayerSymbol);
			
			// Check if game is over
			terminalResults = isTerminalState(state);
			if(terminalResults == "x" || terminalResults == "o" || terminalResults == "c"){
				gameOver = true;
			}
			// Switch whose turn it is
			currPlayerSymbol = otherPlayer(currPlayerSymbol);
		}
	}
	showResults(state, terminalResults);
}

//switch players
proc otherPlayer(player){
	if (player == 'x'){
		return 'o';
	} else {
		return 'x';
	}
}

proc showResults(state, result){
	writeln();
	printState(state);
	if (result == 'c'){
		writeln("\n****************\nCat game. Nobody wins.\n****************\n");
	} else {
		writeln("\n****************\nThe winner is: ", result, "\n****************\n");
	}
}

//Make an empty state
proc makeInitState(){
	var gameBoard : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
   	forall i in [0..NUM_COLS-1]{
   		forall j in [0..NUM_ROWS-1]{
			gameBoard[i][j] = "_";
		}
	}
	return gameBoard;
}

//Get the list corresponding to a column with the given colID
proc getColumn(state, colID){
	return state[colID][0..NUM_ROWS-1];
}

// Get the piece at the current position (might be 'x', 'o', or '_')
proc getPiece(state, colID, rowID){
	return getColumn(state, colID)[rowID];
}

//Neatly print out the board state
proc printState(state){
	// print column headings
	for i in [0..NUM_COLS-1]{
		write(i + " ");
	}
   	writeln();
	
   	for rowID in [0..NUM_ROWS-1]{
      		for colID in [0..NUM_COLS-1] {
        		 write(getPiece(state, colID, rowID) + " ");
		}
     		 writeln();
	}
}

//Copy the state so it may be changed without messing up the original
proc stateCopy(state){
	var newState : [0..NUM_COLS-1][0..NUM_ROWS-1] string;
	newState[0..NUM_COLS-1][0..NUM_ROWS-1] = state[0..NUM_COLS-1][0..NUM_ROWS-1];
	return newState;
}

//Changes (mutates) state to reflect the given move (indicated by colID, done by player
//'x' or 'o').  If the requested column is full, the request is ignored.
proc move(state, colID, player){
	if(!isFullCol(state, colID)){
      		var boardCol = getColumn(state, colID);
     	 	var rowID : int = getLowestRowInCol(boardCol);
      		state[colID][rowID] = player;
	}
}

//Returns row in which a move may be made for this column, or false if the column is full
proc getLowestRowInCol(boardCol){
	//Start at top row (rowID == 0), and go down until you find a piece
	var piece : string;
	var rowID : int;
	var finalRowID : int;
	
	for rowID in [0..NUM_ROWS-1] {
		finalRowID = rowID;
      		piece = boardCol[rowID];
     		 if(piece == 'x' || piece == 'o'){
         		if(rowID == 0){
            			return false;    //column full
         		} else {
            			return rowID-1; 	//Just above current row is open
			}
		}
		//else still looking for top piece
	}
	
	//writeln("\nLOWEST ROW IN COL: ", finalRowID);
	return finalRowID;    //No pieces in this column at all, so return NUM_ROWS-1
}       

//Returns true if the move is valid (correct input type and not a full column).
proc isValidMove(state, colID){
	//if(type(colID) != type(1) || colID < 0 || colID > NUM_COLS - 1){
   	if(colID < 0 || colID > NUM_COLS - 1){
      		return false;
   	} else {
      		return !isFullCol(state, colID);
	}
}

//Returns true if the given column is full in the given state, false otherwise.
proc isFullCol(state, colID){
    return getColumn(state, colID)[0] != '_';
}

//////////////////////////////////////////////////////////////////

//Returns 'x' if x won, 'o' if o won, False if no one has won, and 'c' for a tie
proc isTerminalState(state){
	var blankSpace = false;
	var seq = 1;
	var basePiece : string;
	
	// Test horizontal
	for colID in [0..NUM_COLS-4]{
		for rowID in [0..NUM_ROWS-1]{
			basePiece = getPiece(state, colID, rowID);
			if basePiece != "_"{
				while basePiece == getPiece(state, colID + seq, rowID) {
					seq = seq + 1;
					if seq == 4 {
						return basePiece;
					}
				}
				
				// restart sequence
				seq = 1;
				
			} else {
				blankSpace = true;
			}
		}
	}
	
	seq = 1;
	
	// Test vertical
	for rowID in [0..NUM_ROWS-4]{
		for colID in [0..NUM_COLS-1]{
			basePiece = getPiece(state, colID, rowID);
			if basePiece != "_"{
				while basePiece == getPiece(state, colID, rowID + seq) {
					seq = seq + 1;
					if seq == 4 {
						return basePiece;
					}
				}
				
				// restart sequence
				seq = 1;
				
			} else {
				blankSpace = true;
			}
		}
	}
	
	seq = 1;
	
	// Test up and right
	for colID in [0..NUM_COLS-4]{
		for rowID in [4..NUM_ROWS-1] by -1 {
			basePiece = getPiece(state, colID, rowID);
			if basePiece != "_"{
				while basePiece == getPiece(state, colID + seq, rowID - seq) {
					seq = seq + 1;
					if seq == 4 {
						return basePiece;
					}
				}
				
				// restart sequence
				seq = 1;
			} else {
				blankSpace = true;
			}
		}
	}
	
	seq = 1;
	
	// Test down and right
	for colID in [0..NUM_COLS-4]{
		for rowID in [0..NUM_ROWS-4]{
			basePiece = getPiece(state, colID, rowID);
			if basePiece != "_"{
				while basePiece == getPiece(state, colID + seq, rowID + seq) {
					seq = seq + 1;
					if seq == 4 {
						return basePiece;
					}
				}
				
				// restart sequence
				seq = 1;
				
			} else {
				blankSpace = true;
			}
		}
	}
	
	if (blankSpace) {
		return "*";		// game is not over
	} else {
		return "c";		// cat game
	}
}

//Does an "or" on a list of booleans, except that when it finds anything non-False, it
//returns it, instead of returning True.
proc orList(boolList){
	for b in boolList do{
      if (b){
         return b;
		}
	}
   return false;
}




////////////////////////////////////////////////////////////////////////////////
// Player definitions

//Any player definition should inherit from this class, and define the
//getMove method.

//HumanDef asks for the move to be input from the keyboard
class HumanDef {
   proc HumanDef(playerSymbol){
		var playerSymbol : string;
		playerSymbol = playerSymbol;
		//super(HumanDef).GeneralTestDef(playerSymbol);
	}
	proc getMove(state){
		var move : int;
		write("Enter move: ");
		return read(int);
	}

   proc invalidMoveResponse(){
      writeln("Invalid move, human.  Try again. ");
	}
}


//RandomDef randomly (stupidly) selects a move until a valid one is found
//class RandomDef{
//
//	var rand : RandomStream;
//	//var time : Time;
//	
//	proc RandomDef(playerSymbol){
//		var playerSymbol : string;
//		playerSymbol = playerSymbol;
//		rand = new RandomStream(6);
//		
//		
//		//super(RandomDef).GeneralTestDef(playerSymbol);
//	}
//
//	proc getMove(state){
//        	return RandomStream(int(rand.getNext)%6);    //get random move - will keep trying until valid
//	}
//    
//	proc invalidMoveResponse(){
//       	return;   // No response to invalid move - just try again
//	}
//}


//Then to run a game all should need is this (?)
proc main() {
	playGame(makeInitState(), 'x', new HumanDef('x'), new HumanDef('o'));
}

/////////////////////////////////////////////////////////////////////////

// Debugging functions

//Make a state, given a history of moves.
//X always moves first.  History is a list of columns in which moves were made.
proc makeState(history){
   var players = ['x', 'o'];
   var state = makeInitState();
   var playerID : int = 0;
	for aMove in history {
      move(state, aMove, players(playerID));
      playerID = (playerID + 1) % 2;
	}
	return state;
}

// proc testGetNSeqTests(){
// 	state = makeInitState();
// 	var result: string;
// 	for rowID in 0..NUM_ROWS-1{
// 		for colID in 0..NUM_COLS-1{
// 			tests = getNSeqTests(4, state, colID, rowID);
// 			result = "";
// 			for t in tests{
// 				if (t == isNSeqHoriz){
//                result += 'h';
// 				} else if (t == isNSeqVert){
//                result += 'v';
// 				} else if (t == isNSeqUpRight){
//                result += 'u';
// 				} else if (t == isNSeqDownRight){
//                result += 'd';
// 				}
// 			}
// 			for i in 0..4-len(tests){
//             result += '_';
// 			}
// 			writeln(result + " ");
// 			
// 		}
// 		writeln();
// 	}
// }
// 
//
// proc testIsGeneralNSeq(){
// 	//vertNSeq at col 6, row 2
// 	//horizNSeq at col 3, row 5
// 	//upRightNSeq at col 3, row 5
// 	//downRightNSeq at col 3, row 2
//                 // top -> bottom
//     testState = [['_', '_', '_', '_', '_', '_'], // col 0
//                  ['_', '_', '_', '_', '_', '_'],
//                  ['_', '_', '_', '_', '_', '_'], 
//                  ['_', '_', 'x', 'o', 'o', 'x'], 
//                  ['_', '_', '_', 'x', 'x', 'x'],
//                  ['_', '_', '_', 'x', 'x', 'x'],
//                  ['_', '_', 'x', 'x', 'x', 'x']]; // col 7
// 	printState(testState);
//    writeln(isNSeqVert(4, testState, 6, 2));
//    writeln(isNSeqHoriz(4, testState, 3, 5));
//    writeln(isNSeqDownRight(4, testState, 3, 2));
//    writeln(isNSeqUpRight(4, testState, 3, 5));
// }
// 
// proc testCatGame(){
//     testState = [['x', 'x', 'x', 'o', 'o', 'o'], // col 0
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o'], 
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o'], 
//                  ['o', 'o', 'o', 'x', 'x', 'x'],
//                  ['x', 'x', 'x', 'o', 'o', 'o']]; // col 7
// 	writeln(isTerminalState(testState));
// }
